#include "string"
#include <vector>
#include <iostream>

using namespace std;
void swapChars(std::string & inputString, int currentPosition, int newPosition)
{
	char temp = inputString[newPosition];
	inputString[newPosition] = inputString[currentPosition];
	inputString[currentPosition] = temp;
}

void printAnagrams( std::string & inputString, unsigned int startIndex)
{
    if( startIndex == inputString.size() )
    {
        cout<<inputString<<endl;
        return;
    }
    for( unsigned int index = startIndex; index < inputString.size(); index++ )
    {
        swapChars( inputString,startIndex, index );
        printAnagrams( inputString, startIndex + 1 );
        swapChars( inputString, startIndex, index );
    }
}

void printAnagrams_fixed( std::string & inputString, unsigned int startIndex)
{
    if( startIndex == inputString.size() )
    {
        cout<<inputString<<endl;
        return;
    }
	bool hashMap [256] ;
	for ( int i=0 ; i < 256; ++i)
	{
		hashMap[i] = false;
	}
	for( unsigned int index = startIndex; index < inputString.size(); index++ )
    {
		if(true == hashMap[inputString[index]] )
		{
			continue;
		}
		hashMap[inputString[index]] = true;
        swapChars( inputString,startIndex, index );
        printAnagrams_fixed( inputString, startIndex + 1 );
        swapChars( inputString, startIndex, index );
    }
}

void printAnagramsDynamic( std::string & inputString)
{
	vector<string>	previousStepResults;
	vector<string>  currnetStepResults;
	for( unsigned int i = 0; i < inputString.size(); i++ )
    {
		char ch = inputString[i];
		for (unsigned int j=0; j < previousStepResults.size() ; ++j)
		{
			string prevResult = previousStepResults[j];

			for (unsigned int k = 0 ; k < prevResult.length() ; ++k)
			{
				 string permutedResult = prevResult;
				// permutedResult.insert(k,ch);
				 currnetStepResults.push_back(  permutedResult);
			}
			currnetStepResults.push_back(  prevResult + ch);
		}
    }
}

int main()
{
	std::string str("ABC");
	printAnagramsDynamic(str);
	return 0;
}